//defining the class tree, Node, modules Node and End

abstract class Tree[+T]

//Prefixing a formal type parameter with a + indicates that subtyping is covariant
//(flexible) in that parameter, i.e., any subtype can also be used.

case class Node[+T](value: T, left: Tree[T], right: Tree[T]) extends Tree[T] {
  override def toString = "->(" + value.toString + " " + left.toString + " " + right.toString + ")"
}

case object End extends Tree[Nothing] {
  override def toString = "."
}

object Node {
  def apply[T](value: T): Node[T] = Node(value, End, End)
}

//This code creates the required tree.